import java.util.*;

/**
 * 1726. 同积元组
 * https://leetcode-cn.com/problems/tuple-with-same-product/
 */
public class Solutions_1726 {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, 4, 6};  // output: 8
        int[] nums2 = {1, 2, 4, 5, 10};  // output: 16
        int[] nums3 = {2, 3, 4, 6, 8, 12};  // output: 40
        int[] nums4 = {2, 3, 5, 7};  // output: 0

        List<int[]> list = new ArrayList<>();
        list.add(nums1);
        list.add(nums2);
        list.add(nums3);
        list.add(nums4);
        for (int[] nums : list) {
            int result = tupleSameProduct(nums);
            System.out.println(result);
        }
    }

    /**
     * 解法三：排序（132ms）
     */
    public static int tupleSameProduct(int[] nums) {
        int len = nums.length;
        // nums 中不同元素共有 len 个，那么两数相乘，得到的乘积数共有 maxProductCounts 个
        int maxProductCounts = ((1 + (len - 1)) * (len - 1)) / 2;
        int[] arr = new int[maxProductCounts];
        int idx = 0;
        // 排列组合，获取到所有的两数相乘的结果
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                arr[idx ++] = nums[i] * nums[j];
            }
        }
        // 1 <= nums[i] <= 10000，那么两数之积不可能为 0
        Arrays.sort(arr);
        int res = 0, sameProduct = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                sameProduct ++;
                res += sameProduct * 8;
            } else {
                sameProduct = 0;
            }
        }
        // 不要忽略最后一位元素，因为其没有在 for 循环内进行计算
        res += sameProduct * 8;
        return res;
    }

    /**
     * 解法二：哈希表优化（185ms）
     */
    public static int tupleSameProduct3(int[] nums) {
        // 2 个不同数时，最多的乘积数量为 1：(1 + (2 - 1)) * (2 - 1) / 2 = 1
        // 3 个不同数时，最多的乘积数量为 3：(1 + (3 - 1)) * (3 - 1) / 2 = 3
        int len = nums.length;
        if (len < 4) {
            return 0;
        }
        // 阶梯公式
        int maxProductCounts = ((1 + len - 1) * (len - 1)) / 2;

        Map<Integer, Integer> map = new HashMap<>(maxProductCounts);
        int res = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int product = nums[i] * nums[j];
                int cnt = map.getOrDefault(product, 0);
                res += cnt * 8;
                map.put(product, cnt + 1);
            }
        }
        return res;
    }

    /**
     * 解法一：哈希表（309ms）
     */
    public static int tupleSameProduct2(int[] nums) {
        if (nums == null || nums.length < 4) {
            return 0;
        }
        // {12, 2}，表示 nums 中两数之积为 12 的数对有 2 个
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;

        // 两数之积的所有可能
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                map.put(nums[i] * nums[j], map.getOrDefault(nums[i] * nums[j], 0) + 1);
            }
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int cnt = entry.getValue();
            // 减 1
            cnt -= 1;
            if (cnt > 0) {
                // 两两组合，可以得到的数量
                res += (1 + cnt) * cnt / 2;
            }
        }
        // 为什么乘 8？一个元组有 8 种排列情况
        return res * 8;
    }
}
